Міністерство освіти і науки України
Національний університет „Львівська політехніка”
Звіт
Лабораторна робота № 2
"Параметри та характеристики складності алгоритму. ".
Виконав: ст.гр. КІ-3
Львів
2008
Мета роботи : Засвоєння основних визначень. Порівняння часової складності алгоритмів.
Теоретична частина.
Деяка змінна величина яка визначає значення характеристик математичного об’єкту називається параметром.
Параметри алгоритму.;
система вхідних даних;
система результатів;
система поміжних результатів;
правило початку;
правило закінчення;
правило вводу даних;
правило виводу результатів;
правило безпосереднього перетворення.
Кількість операцій яка потрібна для розв’язку алгоритму називається часова складність.
Складність логіки побудови алгоритму, різноманітність його операцій, зв’язаність їх між собою. Ця характеристика алгоритму називається програмною складністю.
Часова складність визначає час розв’язання задачі, - програмна складність характеризує ступінь інтелектуальних зусиль, що потрібні для синтезу алгоритму.
Приклад знаходження НСД двох чисел методом Евкліда
R0 =A , R1=B, i=1
Ri-1 =Ri * Gi + Ri+1
якщо Ri+1 > 0,то {i=i+1, на пункт 2}
НСД (А,В) = Ri
Нехай ми маємо два довільних числа 99 і 66
99 = 66 * 1 + 33
66 = 33 * 2 + 0 ; появилася ознака – остача 0 то множене і є НСД.
блок-схема алгоритму знаходження найбільшого спільного дільника (НСД)
двох чисел методом перебору, починаючи з 1
SHAPE початок
z і x
iu!=z,iu!=x
iu=iu+1
z%iu=0; x%iu=0
q=iu
Вивести НСД(iu)
кінець
так
ні
так
ні
Програмна складність 5
}блок-схема алгоритму знаходження найбільшого спільного дільника (НСД)
двох чисел методом перебору з, починаючи з меншого числа
C SHAPE початок
z і x
z>x
iu=x
iu=z
q!=0
q=0
Вивести НСД
кінець
ні
так
так
ні
z%iu==0,
x%iu==0
ні
так
програмна складність N=7
блок-схема алгоритму знаходження найбільшого спільного дільника (НСД)
двох чисел методом алгоритму Евкліда
SHAPE початок
z і x
x<z
iu=x; x=z; z=iu;
x%z=0
rez=b
x=z;
z=q;
Вивести
НСД
кінець
так
так
ні
ні
програмна складність N=7
Знаходженя НСД двох чисел методом перебору починаючи з 1(за блок схемою):
-часова складність – (операцій)час виведений в програмі.
-програмною складністю:
1.додавання, віднімання = 1
2. множення, ділення, визначення остачі = 2;
3. порівняння = 2;
Знаходженя НСД двох чисел методом перебору починаючи з меншого(за блок схемою):
- часова складність – (операцій)час виведений в програмі.
- програмною складністю:
1.додавання, віднімання = 1;
2. множення, ділення, визначення остачі = 2;
3. порівняння = 1;
Знаходження НСД двох чисел методом Евкліда(за блок схемою):
- часова складність – (операцій)час виведений в програмі.
- програмною складністю:
1.додавання, віднімання = 0;
2. множення, ділення, визначення остачі = 1;
3. порівняння = 1;
Перших два алгоритми мало відрізняються один від одного. Алгоритм Евкліда є ефективнішим. Так як в ньому найменший різновид використаних операцій.
Додаток:
Програма:
#include <stdio.h>
#include <conio.h>
#include <time.h>
int min(int,int);
int min2(int,int);
int Evklid(int,int);
int main()
{
int a,x=0, t,b, c;
printf("Vvedit 1-she chuslo: ");//scanf("%d", &a);a=2534;
printf("\nVvedit 2-he chuslo: ");//scanf("%d", &b);b=756;
t=time(0);
while(x!=19439){
c=min(a,b);
x++;
}
t=time(0)-t;
t=t*1000000000/x;
printf("%d",t);
printf("\n%d",c);
t=time(0);
x=0;
while(x!=12590){
c=min2(a,b);
x++;
}
t=time(0)-t;
t=t*1000000000/x;
printf("\n%d",t);
printf("\n%d",c);
x=0;
t=time(0);
while(x!=599000){
c=Evklid(a,b);
x++;
}
t=time(0)-t;
t=t*1000000000/x;
printf("\n%d",t);
printf("\n%d",c);
getch();
return 0;
}
int min(int z, int x)
{
int q=1, iu;
if(z>x) iu=x;
else iu=z;
for(;q!=0;iu--){
if(z%iu==0)if(x%iu==0)q=0;...
